package com.icecoding.linked_lists;

import java.util.List;
import java.util.PriorityQueue;

/**
 * 23.合并k个有序链表
 */
public class mergeKLists {
    ListNode mergeKListsSolution(List<ListNode> lists) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.toArray().length, (a, b) -> a.val - b.val);
        for(ListNode head : lists){
            if (head != null){
                pq.add(head);
            }
        }
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            p.next = node;
            p = p.next;
            if (node.next != null){
                pq.add(node.next);
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        mergeKLists mergeKLists = new mergeKLists();
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        ListNode l3 = new ListNode(2);
        l3.next = new ListNode(6);
        ListNode result = mergeKLists.mergeKListsSolution(List.of(l1, l2, l3));
        while(result != null){
            System.out.println(result.val);
            result = result.next;
        }
    }
}
class ListNode{
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}